/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
// 构造二叉树
function buildTree(preorder, inorder) {
  // 使用一个 Map 来存储中序遍历中每个值的索引，方便快速查找
  const inorderIndexMap = new Map();
  for (let i = 0; i < inorder.length; i++) {
    inorderIndexMap.set(inorder[i], i);
  }

  // 定义递归函数
  function helper(preStart, preEnd, inStart, inEnd) {
    // 如果前序或中序范围为空，返回 null
    if (preStart > preEnd || inStart > inEnd) return null;

    // 前序遍历的第一个元素是当前子树的根节点
    const rootVal = preorder[preStart];
    const root = new TreeNode(rootVal);

    // 找到根节点在中序遍历中的位置
    const inRootIndex = inorderIndexMap.get(rootVal);

    // 左子树的节点数量
    const leftSubtreeSize = inRootIndex - inStart;

    // 递归构建左子树
    root.left = helper(
      preStart + 1, // 左子树的前序起点
      preStart + leftSubtreeSize, // 左子树的前序终点
      inStart, // 左子树的中序起点
      inRootIndex - 1 // 左子树的中序终点
    );

    // 递归构建右子树
    root.right = helper(
      preStart + leftSubtreeSize + 1, // 右子树的前序起点
      preEnd, // 右子树的前序终点
      inRootIndex + 1, // 右子树的中序起点
      inEnd // 右子树的中序终点
    );

    return root;
  }

  // 调用递归函数，初始范围为整个数组
  return helper(0, preorder.length - 1, 0, inorder.length - 1);
}
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * 从前序和中序遍历序列构造二叉树
 * @param {number[]} preorder - 前序遍历数组
 * @param {number[]} inorder - 中序遍历数组
 * @return {TreeNode} - 返回构造好的二叉树根节点
 */
// 这个是从谦虚和中序遍历序列构造二叉树
// 但是我觉得这个还是不太好，因为不太好理解这个东西
// 不管是 ai 写的还是我自己写的，都是不太好阅读的
var buildTree = function (preorder, inorder) {
  // 递归终止条件：如果前序或中序数组为空，说明当前子树为空
  if (preorder.length === 0 || inorder.length === 0) {
    return null;
  }

  // 前序遍历的第一个元素总是当前子树的根节点
  const rootVal = preorder[0];
  const root = new TreeNode(rootVal);

  // 在中序遍历中找到根节点的位置，用于划分左右子树
  // 中序遍历的特性：左子树节点都在根节点左侧，右子树节点都在根节点右侧
  const inorderRootIndex = inorder.indexOf(rootVal);

  // 划分中序遍历数组：
  // 左子树的中序遍历是从开始到根节点位置之前
  const leftInorder = inorder.slice(0, inorderRootIndex);
  // 右子树的中序遍历是从根节点位置之后到末尾
  const rightInorder = inorder.slice(inorderRootIndex + 1);

  // 划分前序遍历数组：
  // 前序遍历的特性：根节点之后紧跟着左子树节点，然后是右子树节点
  // 左子树的节点数量等于中序遍历中左子树的长度
  const leftPreorder = preorder.slice(1, leftInorder.length + 1);
  // 剩下的元素就是右子树的前序遍历
  const rightPreorder = preorder.slice(leftInorder.length + 1);

  // 递归构建左子树和右子树
  root.left = buildTree(leftPreorder, leftInorder);
  root.right = buildTree(rightPreorder, rightInorder);

  // 返回当前构建的根节点
  return root;
};